#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE  20
typedef int Elemtype;
typedef struct BiTNode{
    Elemtype data;
    struct BiTNode *lchild;
    struct BiTNode * rchild;
}BiTNode,*BiTree;

void visit(Elemtype data){
    printf("  %d  ",data);
}

void preOrder(BiTree T){
    if(T!=NULL){
    visit(T->data);
    preOrder(T->lchild);
    preOrder(T->rchild);
    }
}

void inOrder(BiTree T){
 if(T!=NULL){
    inOrder(T->lchild);
    visit(T->data);
    inOrder(T->rchild);
    }
}

void postOrder(BiTree T){
 if(T!=NULL){
    postOrder(T->lchild);
    postOrder(T->rchild);
    visit(T->data);
    }
}

typedef struct node
{
    BiTNode* data;
    struct node *next;
}node;

typedef struct Queue{
    node *front;
    node *rear;
}Queue;

node* initNode(){
    node *n = (node*)malloc(sizeof(node));
    return n; 
}

Queue* initQueue(){
    Queue *q = (Queue*)malloc(sizeof(Queue));
    q->front = NULL;
    q->rear = NULL;
    return q;
}

int isEmpty(Queue *q){
    if(q->front ==NULL){
        return 1;
    }
    return 0;
}
//入队
void EnQueue(Queue*q,BiTNode*data){
    node *n = initNode();
    n->data = data;n->next = NULL;
    if(isEmpty(q)){
        q->front = n;
        q->rear = n;
    }else{
        q->rear->next = n;
        q->rear = n;
    }

}
//出队
BiTNode * DeQueue(Queue *q){
    node *n = q->front;
    if(isEmpty(q)){
        return NULL;
    }
    BiTNode* res = n->data;
    if(q->front == q->rear){
        q->front = NULL;
        q->rear = NULL;
    }else{
        q->front = q->front->next;
    }
    free(n);
    return res;

}

void levelTraverse(BiTree T){
        Queue *Q = initQueue();
        if(T!=NULL){
            EnQueue(Q,T);
        }
        while (!isEmpty(Q))
        {
           BiTNode*e = DeQueue(Q);
           visit(e->data);
           if(e->lchild!=NULL){
            EnQueue(Q,e->lchild);
           }
           if(e->rchild!=NULL){
            EnQueue(Q,e->rchild);
           }
        }
}


//通过中序遍历和先序遍历来创建二叉树
BiTNode * createBiTree(Elemtype preOrderarr[],int preFirst,int preLast,
 Elemtype inOrderarr[],int inFirst , int inLast){

        if(preFirst > preLast){
            return NULL;
        }
        BiTNode * root = (BiTNode *)malloc(sizeof(BiTNode));
        root->data = preOrderarr[preFirst];
        int rootIndex; //寻找根节点在中序序列的索引
        for ( rootIndex = inFirst; rootIndex <= inLast; rootIndex++)
        {
           if(root->data == inOrderarr[rootIndex]){
                break;
           }
        }
        BiTNode * lchild = createBiTree(preOrderarr,preFirst+1,preFirst+rootIndex-inFirst,
        inOrderarr,inFirst,rootIndex-1);
        BiTNode * rchild = createBiTree(preOrderarr,preFirst+rootIndex-inFirst+1,preLast,
        inOrderarr,rootIndex+1,inLast);
        root->lchild = lchild;
        root->rchild = rchild;
        return root;
}

/*
树的路径确定、图的路径 ： 栈或数组
int path[MAXSIZE];
int length = 0;

void function(int length){

path[length++] = pnode->data;
...



}

*/
//栈的初始化
typedef struct SqStack
{
   BiTNode * data[MAXSIZE];
   int top;
}SqStack, *Stack;


//创建栈
Stack initStack(){
    Stack s;
    s = (Stack)malloc(sizeof(SqStack));
    s->top = -1;
    return s;
}

//栈空
int isStackEmpty(Stack s){
    if(s->top == -1){
        return 1;
    }
    return 0;
}

//入栈
void push(Stack s,BiTNode* p){
    s->top++;
    s->data[s->top] = p;
}
//出栈
void pop(Stack s,BiTNode** p){
    *p = s->data[s->top];
    s->top--;
}

// 树的非递归遍历

//先序非递归遍历
void preOrder02 (BiTree T){
    BiTNode *pNode = T;
    Stack stack = initStack();
    while (pNode!=NULL || !isStackEmpty(stack))
    {
       if(pNode){
            push(stack,pNode);
            visit(pNode->data);
            pNode = pNode->lchild;
       }else{
            pop(stack,&pNode);
            pNode = pNode->rchild;
       }
    }
}

//中序非递归遍历
void inOrder02 (BiTree T){
    BiTNode *pNode = T;
    Stack stack = initStack();
    while (pNode!=NULL || !isStackEmpty(stack))
    {
       if(pNode){
            push(stack,pNode);
            pNode = pNode->lchild;
       }else{
            pop(stack,&pNode);
            visit(pNode->data);
            pNode = pNode->rchild;
       }
    }
}

//后序非递归遍历 
//左子树- 右子树 - 根
void postOrder02(BiTree T){
    BiTNode *pNode = T; 
    BiTNode *r = NULL; //这个r是最后访问的节点，用来判断某个根节点pnode的右子树是否被访问,因为右子树访问结束之后，最后 一个被访问的节点一定是右子树的根节点，也就是pnode的右孩子。
    Stack stack = initStack();
    while (pNode!= NULL || !isStackEmpty(stack))
    {
       if(pNode){
        //寻找最左下的节点
            push(stack,pNode);
            pNode = pNode->lchild;
       }else{
         //先获取栈中最顶上的节点，看他有没有右子树
          pop(stack,&pNode);//此时 pNode 是 左子树已经访问完毕的树的根节点
          push(stack,pNode);
          if(pNode->rchild && pNode->rchild!= r){
            // 右子树是存在的且右子树没有被访问过，那么先访问右子树再访问根节点
            pNode = pNode->rchild; //切换到右子树的根节点
            push(stack,pNode);//对于一个子树来说，根是最后访问的，先访问左子树
            pNode = pNode->lchild;//切换到左子树的根节点
          }else{
            //如果右子树为空或者右子树已经访问过了，那就访问根节点
            pop(stack,&pNode);
            visit(pNode->data);
            r = pNode;
            pNode = NULL; //当前被打印的节点一定是子树的根节点
            /*
            如果是左子树的根节点 ： 那么某个树的左子树被遍历完了，就要看他有没有右子树要遍历
            如果是右子树的根节点：  那么某个树的右子树被遍历完了，就要遍历他自己了
            */
          }
       }
    }
}
//求二叉树的节点数量
int getTreeNodes(BiTree T){
    if(T== NULL){
        return 0;
    }
    return getTreeNodes(T->lchild) + getTreeNodes(T->rchild) +1;
}

//求叶子节点数量
int getLeaveNodes(BiTree T){
    if(T == NULL){
        return 0;
    }
    if(T->lchild == NULL && T->rchild == NULL){
        return 1;
    }
    return getLeaveNodes(T->lchild) + getLeaveNodes(T->rchild);
}

//层次遍历 + 中序遍历确定二叉树
BiTree createBiTree02(Elemtype levelOrderarr[],int levelFirst,int levelLast,
 Elemtype inOrderarr[],int inFirst , int inLast){

    if(levelFirst > levelLast){
        return NULL;
    }
    //每次递归确定一个根节点
    BiTNode * root = (BiTNode*)malloc(sizeof(BiTNode));
    root->data = levelOrderarr[levelFirst];
    //在中序遍历中寻找根节点的位置，划分左右子树
    int rootIndex =  inFirst;
    for (; rootIndex <= inLast; rootIndex++)
    {
       if(inOrderarr[rootIndex] == root->data){
        break;
       }
    }  
    //层次遍历中左右子树的遍历序列和先序序列分别相等
    //使用两个数组，分别存储层次遍历中的左子树遍历的序列和右子树遍历的序列
    Elemtype leftLevelOrderList[MAXSIZE];
    int leftLength = 0;
    //遍历中序序列对比找到左子树的所有元素
    for (int i = levelFirst + 1; i <= levelLast; i++)
    {
        for (int j = inFirst; j <= rootIndex; j++)
        {
           if(levelOrderarr[i] == inOrderarr[j]){
                leftLevelOrderList[leftLength++] = levelOrderarr[i]; 
           }
        }
    }
    Elemtype rightLevelOrderList[MAXSIZE];
    int rightLength = 0;
    //遍历中序序列对比找到右子树的所有元素
    for (int i = levelFirst + 1; i <= levelLast; i++)
    {
        for (int j = rootIndex+1; j <= inLast; j++)
        {
           if(levelOrderarr[i] == inOrderarr[j]){
                rightLevelOrderList[rightLength++] = levelOrderarr[i]; 
           }
        }
    }
    //递归创建左右子树的根节点
    root->lchild = createBiTree02(leftLevelOrderList,0,leftLength-1,inOrderarr,inFirst,rootIndex-1);
    root->rchild = createBiTree02(rightLevelOrderList,0,rightLength-1,inOrderarr,rootIndex+1,inLast);
    return root;
}

/*
是否为空树
    空树  -不影响结果
    非空树  分类根据题目要求
          度为0
          度为1
          度为2  
*/
//统计度为1的节点数
int getSingleDegreeNode(BiTree T){
    if(T == NULL){
        return 0;
    }else if (T->lchild != NULL && T->rchild==NULL)
    {
       return 1 + getSingleDegreeNode(T->lchild);
    }else if (T->lchild == NULL && T->rchild!=NULL)
    {
       return 1 + getSingleDegreeNode(T->rchild);
    }else{
        //度为2或者度为0
        return getSingleDegreeNode(T->lchild) +getSingleDegreeNode(T->rchild);
    }
}

BiTNode * getXNode(BiTree T,Elemtype x){
    if(T==NULL){
        return NULL;
    }
    else if (T->data == x)
    {
      return T;
    }else{
      BiTNode * leftRes = getXNode(T->lchild,x);
      if(leftRes!=NULL){
        return leftRes;
      }  
      return getXNode(T->rchild,x);
    }
}

int getHeight(BiTree T){
    if(T == NULL){
        return 0;
    }
    int leftHeight = getHeight(T->lchild);
    int rightHeight =getHeight(T->rchild);
    int res = leftHeight > rightHeight ? leftHeight :rightHeight;
    return  res + 1;
}


//完全二叉树的判断
int isComplete(BiTree T){
        Queue *Q = initQueue();
        if(T!=NULL){
            EnQueue(Q,T);
        }
        while (!isEmpty(Q))
        {
           BiTNode*e = DeQueue(Q);
          
           if(e == NULL){
            break;
           }
         
            EnQueue(Q,e->lchild);
            EnQueue(Q,e->rchild);
        }

        while (!isEmpty(Q))
        {
           BiTNode *e = DeQueue(Q);
           if(e != NULL){
            return 0;
           }
        }
        return 1;  
}

int main(){
    int preArr[MAXSIZE] = {1,2,4,5,7,3,6};
    int inArr[MAXSIZE] = {4,2,7,5,1,3,6}; 
    int levelArr[MAXSIZE] = {1,2,3,4,5,6,7}; 
    // int inArr[MAXSIZE] = {4,2,5,1,7,3,6}; 
    // int levelArr[MAXSIZE] = {1,2,3,4,5,7,6};    
    BiTree T =  createBiTree02(levelArr,0,6,inArr,0,6);

   printf(" the res is %d\n",isComplete(T));
}
